1. Field of the Invention
The present invention relates to a message authorization system for authorizing a message for an electronic document and, more particularly, to a message authorization system which enables designation of a verifier of authorization data without communication between a verifier and a sender. The invention also relates to a message authorization system for signing an electronic document using such a message authorization system.
2. Description of the Related Art
Message authentication is used by a sender for disclosing an electronic document only to a specific verifier. Message authentication is different from common digital signature by which anyone can verify signature data in that a sender can limit a verifier and that even if a verifier transfers authentication data for reading an electronic document in question to a third party, the third party is incapable of verifying the authentication data.
Typical message authentication system is disclosed, for example, in Eiji Okamoto, Introduction to Cryptography Theory, Kyoritsu Publishing Company, on pages 129 to 131. According to the literature, a sender and a verifier share an encryption key K in advance and the sender sends a hash value produced from a message and the encryption key K as authentication data together with the message. The verifier calculates a hash value from the received message and the shared encryption key K in the same manner and if the result is equal to the received authentication data, the verifier accepts the data as right authentication data. Even if the authentication data is transferred to a third party, the third party can not distinguish right data which is authorized by a sender from authentication data produced by the verifier by himself and can not verify the authentication data accordingly.
As a method of realizing message authentication without sharing of an encryption key between a sender and a verifier in advance, there is a method disclosed in "How to Utilize Randomness of Zero-Knowledge Proofs" (Okamoto and Ohta, Lecture Notes in Computer Science 537, Advances in Cryptology-CryPto '90, Springer-Verlag, pp. 456-475). The message authentication system recited in the literature realizes message authentication by combining a value obtained from a message with a random number information component in a personal authentication protocol of a sender employing zero-knowledge proofs.
In the above-described conventional message authentication, when employing a system in which a common key is shared in advance, however, flexibility of the system is diminished because a sender and a verifier should share a common key. In addition, communication between a sender and a verifier for setting a common key is required, which makes procedure troublesome.
In a system employing zero-knowledge proofs, personal authentication protocol should be interactively conducted and communication between a sender and a verifier is required accordingly, making procedure troublesome.
Non-interactive execution of personal authentication protocol is recited in the literature "How to Prove Yourself: Practical Solutions to Identification and Signature Problems" (Fiat and Shamir, Advances in Cryptology-Crypto 86, pp. 186-199). Fiat-Shamir system, however, has a drawback that transmitted data, like digital signature, can be verified by anyone.
It is therefore needed to realize a message authentication system which can limit a verifier simply by sending authentication data from a sender to the verifier without communication between them.
For digital signature, an undeniable signing method is proposed which allows a signer to limit a verifier. Unlike common digital signature, undeniable signature is non-divertible, which enables a signer to limit a verifier. Among conventional undeniable signing methods are that proposed by Chaum, that disclosed in Japanese Patent Laying Open (Kokai) No. Heisei 4-237087, entitled "Digital Signing System" and No. Heisei 5-333777, entitled "Digital Signing System". According to these methods, verifier inquires mode of verifying a signature and communicates with a signer to conduct verification. Acceptance or denial of the inquiry by the signer enables selection of a verifier.
According to the digital signing method recited in Japanese Patent Laying Open (Kokai) No. Heisei 4-237087, for example, there is such public information produced by using common information "p" and "g" and a key "x" for signing as follows: EQU y=g.sup.x mod p ( 1)
and signature data "s" will be produced according to the following expression. EQU s mx mod p (2)
For verifying the above data, a verifier and a signer communicate in a manner as described in the following. First, the signer produces the expressions set forth below by using a random number "r" and sends them to the verifier. EQU X1=gr mod p (3) EQU X2=mr mod p (4)
On the other hand, the verifier sends a random number "e". The signer creates a communication document set forth below and sends the document to the verifier. EQU Y=r+e.multidot.x (5)
The verifier conducts verification according to the following expressions. EQU X1.sup.Y =y.sup.e .multidot.g.sup.r mod p (6) EQU X2.sup.Y =s.sup.e .multidot.m.sup.r mod p (7)
According to the digital signing method recited in Japanese Patent Laying Open (Kokai) No. Heisei 5-333777, a signer opens to the public a graph "g" with a key for signing as a Hamilton closed circuit, produces a signature "s" having a Hamilton closed circuit "h" from messages "m", "g" and "h" and transmits the message "m" and the signature "s" to a verifier. The verifier sends the message "m", the signature "s" ad a random number {c} to the signer. Next, the signer calculates graphs "a"=.pi.(g) and "b"=.pi.(s) by substitution .pi., makes the graphs into cryptograms using the random number {c} and sends the cryptograms as "X1", "X2" and "X3" to the verifier. The verifier further sends a random number "q" to the singer. The signer sends the information of "X1", "X2" and "X3" as "Y" to the verifier when "q"=0 in an information presentation device. When "q"=1, if the signature "s" is right, the signer sends, as "Y", information used for a closed circuit .pi.(h) for the graph "a" and the information used for the closed circuit .pi.(h) for the graph "b" to the verifier. When the signature "s" is not right, the signer sends to the verifier, as "Y", the encryption information for the graph "a" and the encryption information of a part of the encryption information for the graph "b" which part is different from the encryption information for the graph "a". The verifier verifies the message "m" and the signature "s" based on "Y", "X1", "X2", "X3" and the random number "q".
The above-described conventional digital signing method, as well as conventional message authentication system, requires communication between a signer and a verifier at the time of verification of a signature of the signer by the verifier, making procedure troublesome.
When verifying a signature by one-way data communication from a signer to a verifier according to the Fiat-Shamir system in order to avoid communication between a signer and a verifier, verification data becomes equal to ordinary digital signature indicating that verification data is universally right or not, hurting non-divertibility of an undeniable signature.
It is therefore needed to realize an undeniable signing method which allows a signer to limit a verifier by simply transmitting verification data from the signer to the verifier without communication between them, that is, to realize a non-divertible digital signing system.